package LeetCode;

import java.util.Arrays;

/**
 * @Author: Dijah
 * @Date: 2023/1/6 11:08
 * @Desc: 最长递增子序列
 */
public class code300_LengthOfLIS {

    public static int lengthOfLIS(int [] nums){
        //使用动态规划填充 dp一维数组，
        //每个位置的dp[i] 代表 以nums[i] 结尾的位置的数字最长递增子序列是几
        int N = nums.length;
        int[] dp = new int[N];
        //填充dp，每个位置都初始化为1
        Arrays.fill(dp,1);
        for(int i =0; i < N; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res = 0;
        //比较dp[i] 位置返回Math.max()
        for(int a = 0; a < dp.length; a++){
            res = Math.max(res,dp[a]);
        }
        return res;
    }

    /**
     * 方法二，想象一堆扑克牌，依次排序，小的只能压到大的下面
     * 每一堆扑克顶部的值的就是递增的子序列
     * 一共有多少堆就是长度
     * https://labuladong.github.io/algo/di-er-zhan-a01c6/zi-xu-lie--6bc09/dong-tai-g-6ea57/
     * @param nums
     * @return
     */
    int lengthOfLIS1(int[] nums) {
        int[] top = new int[nums.length];
        // 牌堆数初始化为 0
        int piles = 0;
        for (int i = 0; i < nums.length; i++) {
            // 要处理的扑克牌
            int poker = nums[i];

            /***** 搜索左侧边界的二分查找 *****/
            int left = 0, right = piles;
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            /*********************************/

            // 没找到合适的牌堆，新建一堆
            if (left == piles) piles++;
            // 把这张牌放到牌堆顶
            top[left] = poker;
        }
        // 牌堆数就是 LIS 长度
        return piles;
    }


    public static void main(String[] args) {
        int [] nums = {10,9,2,5,3,7,101,18};
        int i = lengthOfLIS(nums);
        System.out.println(i);
    }
}
